package leetcode.sever;

import java.util.Arrays;

/**
 * 七期题目列表：
 *  动态规划,对于一个动态规划题目,比较通用的求解步骤如下：
 *      1、确定状态转移公式,当前的状态是怎么由前面的状态变化而来的以及与之相关的辅助的dp数组以及下标的含义。
 *      2、初始化dp数组。
 *      3、根据题目条件开始遍历,并实现状态转移公式。
 */
public class DtghTest {

    public static void main(String[] args) {

    }


    /**
     * leetcode-5 最长回文字串
     * 动态规划实现
     *
     */
    public static String longestPalindrome(String s){
        int len = s.length();
        if (len == 1){
            return s;
        }
        char[] charArray = s.toCharArray();
        if(len == 2){
            if(charArray[1] == charArray[0]){
                return s;
            }else {
                return s.substring(0,1);
            }
        }
        //记录回文字串的长度和起始位置
        int maxLen = 1;
        int begin = 0;
        //dp[i][j] 表示s[i,j]是否是回文串
        boolean[][] dp = new boolean[len][len];
        //dp[i][j]中i==j时，表示起始字符串中的每个字符，当时是回文串。(二位数组的斜对角线)
        for (int i = 0; i < len; i++){
            dp[i][i] = true;
        }
        for (int j = 1; j < len; j++){
            for (int i = 0; i < j; i++){
                if(charArray[i] != charArray[j]){
                    dp[i][j] = false;
                }else {
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                //只要dp[i][j] == true,就表示字串s[i,j]是回文,此时记录回文长度和起始位置
                if(dp[i][j] && j - i + 1 > maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    /**
     * 最长回文字串
     * 已当前字符为中心左右扩展（奇数字符）、或者以空格为中心左右扩展（偶数字符）
     */
    public static String longestPalindrome1(String s){
        int maxStart = 0;
        int maxEnd = 0;
        for (int i = 0; i < s.length(); i++){
            //已当前字符为中心,进行左右扩展
            int charCenterLen = expandAroundCenters(s,i,i);
            int blackCenterLen = expandAroundCenters(s,i,i+1);
            int len = Math.max(charCenterLen,blackCenterLen);
            if(len > maxEnd - maxStart){
                maxStart = i - (len - 1) / 2;
                maxEnd = i + len / 2;
            }
        }
        return s.substring(maxStart,maxEnd + 1);
    }
    private static int expandAroundCenters(String s, int left, int right) {
        while (left >= 0 && right <= s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right - left -1;
    }


    /**
     * Leetcode - 62
     * 不同路径
     * 一个机器人位于一个 m x n网格的左上角,机器人每次只能向下或者向右移动一步,机器人到达网格的右下角
     * 总共有多少条不同的路径
     *
     */
    public static int uniquePaths(int m, int n){
        int[][] dp = new int[m][n];
        //dp数组初始化
        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++){
            dp[0][j] = 1;
        }
        //使用状态转移公式填充DP数组
        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public static int uniquePaths1(int m, int n){
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }

    /**
     * Leetcode - 64
     * 最小路径和
     * 给定一个包含非负整数的 m x n网格,请找出一条从左上角到右下角的路径,使得路径上的数组总和为最小
     * 说明：每次只能向下或者向右移动一步
     *
     */
    public static int minPathSum(int[][] grid){
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        //初始化dp数组
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++){
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int j = 1; j < n; j++){
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }
        //使用状态转移公式填充dp数组
        for (int i =1; i < m; i++){
            for (int j =1; j < n; j++){
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m -1][n - 1];
    }

    /**
     * LeetCode - 91 解码方法
     * 一条包含字母A-Z的消息通过一下映射进行了编码:
     *  'A' ->'1'
     *  'B' ->'2'
     *  .....
     *  'Z' ->'26'
     *  给你一个只含数组的非空字符串s,请计算并返回解码方法的总数。
     *  题目数组保证答案肯定是一个32位的整数
     */
    public static int numDecoding(String s){
        int n = s.length();
        //dp数组要比原始字符串长度大1
        int[] dp = new int[n + 1];
        //初始化dp数组
        dp[0] = 1;
        for (int i =1; i <= n; i++){
            //单独解码原始字符串当前元素
            if (s.charAt(i - 1) != '0'){
                dp[i] = dp[i - 1];
            }
            if(i >= 2){
                //元素的组合转为数字  利用ASI码
                int num = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
                if (num >= 10 && num <= 26){
                    dp[i] += dp[i -2];
                }
            }
        }
        return dp[n];
    }


    /**
     * LeetCode - 152
     * 乘积最大子数组
     * 给你一个整数数组nums,请你找出数组中乘积最大的非空连续子数组,返回该子数组所对应的乘积
     * 字数组是数组的连续子序列。
     *
     */
    public static int maxProduct(int[] nums){
        if (nums.length == 1){
            return nums[0];
        }
        int result = nums[0], max = nums[0], min = nums[0];
        for (int i = 1; i < nums.length; i++){
            int currMax = max * nums[i],currMin = min * nums[i];
            max = Math.max(nums[i], Math.max(currMax, currMin));
            min = Math.min(nums[i], Math.max(currMax,currMin));
            result = Math.max(result, max);
        }
        return result;
    }

    /**
     * LeetCode - 198 打家劫舍
     * 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是
     *      相邻的房屋装有互相连通的防盗系统,如果相邻的房屋在同一个晚上被小偷闯入,系统会自动报警
     *  给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况一夜之内偷窃的最高金额。
     *
     */
    public static int rob(int[] nums){
        int len = nums.length;
        if (len == 1){
            return nums[0];
        }
        if(len == 2){
            return nums[0] > nums[1] ? nums[0] : nums[1];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
        for (int i = 2; i < len; i++){
            dp[i] = Math.max(dp[i - 1], dp[i] + dp[i - 2]);
        }
        return dp[len - 1];
    }
    //双指针
    public static int rob1(int[] nums){
        int len = nums.length;
        if (len == 1){
            return nums[0];
        }
        if(len == 2){
            return nums[0] > nums[1] ? nums[0] : nums[1];
        }
        int prePre = nums[0];
        int pre = nums[0] > nums[1] ? nums[0] : nums[1];
        int curr = 0;
        for (int i = 2; i < len; i++){
            curr = Math.max(pre, nums[i] + prePre);
            prePre = pre;
            pre = curr;
        }
        return curr;
    }

    /**
     * LeetCode - 337 打家劫舍III --树形dp
     * 每栋房子有且只有一个“父”房子与之相连。这个地方的所有房屋的排列类似于一颗二叉树。
     * 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
     * 给定二叉树的root,返回在不触动警报的情况下,小偷能够盗取的最高金额。
     *  后续遍历 + 递归
     */
    public static int rob(TreeNode root){
        int[] result = robNode(root);
        return Math.max(result[0], result[1]);
    }
    //返回值表示当前节点root的结果,用长度为2的数组表示,下标为0表示偷root时的最大值,下标[1]表示不偷root时的最大值
    private static int[] robNode(TreeNode root) {
        if(root == null){
            return new int[]{0,0};
        }
        int[] left = robNode(root.left);
        int[] right = robNode(root.right);
        //偷当前节点root时的值
        int stealCurr = root.val + left[1] + right[1];
        //不偷当前节点root时的值
        int noStealCurr = Math.max(left[0],left[1]) + Math.max(right[0], right[1]);
        return new int[]{stealCurr,noStealCurr};
    }


    /**
     * LeetCode - 300 最长（递增）子序列
     * 给你一个整数数组nums,找到其中最长严格递增子序列的长度
     * 子序列:是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。
     */
    //时间复杂度O(n^2)
    public static int lengthOfLIS(int[] nums){
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < nums.length; i++){
            for (int j = 0; j < i; j++){
                if(nums[i] > nums [j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int result = 0;
        for (int i = 0; i< dp.length; i++){
            result = Math.max(result, dp[i]);
        }
        return result;
    }

    /**
     * 二分查找 + dp实现
     * 时间复杂度O(nlogn)
     */
    public static int lengthOfLIS1(int[] nums){
        int length = nums.length;
        int[] dp = new int[length];
        int result = 1;
        dp[0] = nums[0];
        for (int i = 1; i < length; i++){
            if(nums[i] > dp[result - 1]){
                dp[result] = nums[i];
                result++;
            }else {
                int start = 0, end = result;
                //已二分查找在dp数组中寻找第一个大于nums的元素
                while (start < end){
                    int mid =(start + end) / 2;
                    if(dp[mid] < nums[i]){
                        start = mid + 1;
                    }else {
                        end = mid;
                    }
                }
                dp[start] = nums[i];
            }
        }
        return result;
    }


    /**
     * LeetCode - 121
     * 买卖股票的最佳时机
     * 给定一个数组prices,它的第i个元素prices[i]表示一支给定股票第i天的价格。
     * 你只能选择某一天买入这只股票,并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润
     * 如果不能获取利润返回0
     * 例如：【7,1,5,3,6,4】
     * 输入5：解释在第二天股票价格为1的时候买入，在第5天的时候卖出。
     *        注意利润不能是7-1=6,因为卖出价格需要大于买入价格;同时你不能在买入前卖出股票
     */
    public static int maxProfit(int[] prices){
        if (prices.length < 2){
            return 0;
        }
        int profitMax = 0;
        int min = prices[0];
        for (int i = 0;i < prices.length; i++){
            if(prices[i]>min){
                //当前元素大于当前最小值，看看是否需要更新已知的最大差距
                profitMax = Math.max(profitMax,prices[i] - min);
            }else {
                //当期元素小于等于当前最小值,更新当前最小值
                min = prices[i];
            }
        }
        return profitMax;
    }

    /**
     * LeetCode - 309 最佳买卖股票时机含冷冻期
     *
     */
    public static int maxProfit1(int[] prices){
        // 0-表示卖出不持有
        // 1-表示未动作不持有
        // 2-表示买入持有
        // 3-表示冷冻期不持有
        int length = prices.length;
        int[][] dp = new int[length][4];
        dp[0][2] = -prices[0];
        for (int i =1; i < length; i++){
            dp[i][0] = prices[i] + dp[i - 1][2];
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = Math.max(dp[i - 1][1] - prices[i],
                    Math.max(dp[i - 1][2], dp[i - 1][3] - prices[i]));
            dp[i][3] = dp[i - 1][0];
        }
        return Math.max(dp[length - 1][0],
                Math.max(dp[length - 1][1], dp[length - 1][3]));
    }

    /**
     * LeetCode - 322 零钱兑换（每种硬币的数量是无限的）--与背包问题的区别(背包只能选择一个,不能重复选择)
     * 给你一个整数数组coins,表示不同面额的硬币,以及一个整数amount表示总金额
     * 计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合组成总金额返回-1
     *
     */
    public static int coinChange(int[] coins, int amount){
        int impossible = amount + 1;
        int[] dp = new int[impossible];
        //初始化dp数组值
        Arrays.fill(dp, impossible);
        dp[0] = 0;
        int n = coins.length;
        for (int i = 0; i < n; i++){
            for (int j = 1; j < amount; j++){
                if (j >= coins[i]){
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == impossible ? -1 : dp[amount];
    }


    /**
     * LeetCode - 416 分割等和子集
     * 给你一个只包含正整数的非空数组nums.请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
     *
     */
    public static boolean canPartition(int[] nums){
        int length = nums.length;
        //数组元素只有0个或者1个,直接返回false
        if (length < 2){
            return false;
        }
        //数组元素只有两个,直接判断
        if (length == 2){
            return nums[0] == nums[1] ? true : false;
        }
        //sum统计数组元素和,maxNum记录数组最大数值元素
        int sum = 0, maxNum = 0;
        for (int num : nums){
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        //如果sum为奇数,是不可能分为和为相等的两个子集
        if(sum % 2 != 0){
            return false;
        }
        int target = sum / 2;
        //数组最大数值大于数组元素和的一半,不可能分为和为相等的两个子集
        if (maxNum > target){
            return false;
        }
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < length; i++){
            int num = nums[i];
            if(num >= target){
                //数组存在元素等于数组元素和的一半,一定可以分为相等的两个子集
                return num > target ? false : true;
            }
            for (int j = target; j >= num; j--){
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }

    /**
     * LeetCode - 494 目标和
     * 给你一个整数数组nums和一个整数target,向数组中的每个整数钱添加'+'或者'-',
     * 然后串联起所有整数构造一个表达式,运算结果等于target的不同表达式的数目。
     *
     */
    public static int findTargetSumWays(int[] nums, int target){
        int length = nums.length;
        if(length == 1){
            return nums[0] == target || nums[0] == -target ? 1 : 0;
        }
        //统计数组元素和
        int sum = 0;
        for (int num : nums){
            sum += num;
        }
        //加数集合和 = (target + sum) / 2
        //减数集合和 = (sum - target) / 2
        int diff = sum -target;
        if (diff < 0 || diff % 2 != 0){
            return 0;
        }
        int need = diff / 2;
        int[] dp = new int[need + 1];
        dp[0] = 1;
        for (int num : nums){
            for (int j = need; j >= num; j--){
                dp[j] = dp[j] + dp[j - num];
            }
        }
        return dp[need];
    }

    /**
     * LeetCode - 718 最长重复子数组
     * 给两个整数数组nums1 和 nums2,返回两个数组中的公共的、长度最长的字数组的长度
     * nums1 =[1,2,3,2,1],nums2 = [3,2,1,4,7];
     * 输出3,解释长度最长的公共字数组是[3,2,1]
     *
     */
    public static int findLength(int[] nums1, int[] nums2){
        int length1 = nums1.length;
        int length2 = nums2.length;
        int[] dp = new int[length2 + 1];
        int result = 0;
        for (int i = 1; i < length1; i++){
            for (int j = length2; j > 0; j--){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[j] = dp[j - 1] + 1;
                }else {
                    dp[j] = 0;
                }
                result = Math.max(result,dp[j]);
            }
        }
        return result;
    }

    /**
     * LeetCode - 42 接雨水
     * 给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水
     * 例子：height = [0,1,0,2,1,0,1,3,2,1,2,1];
     * 输出6
     */
    public static int trap(int[] height){
        int length = height.length;
        if (length == 0){
            return 0;
        }
        //正向遍历数组填充dp数组leftDp
        int[] leftDp = new int[length];
        leftDp[0] = height[0];
        for (int i =1; i < length; i++){
            leftDp[i] = Math.max(leftDp[i - 1], height[i]);
        }
        //反向遍历数组填充dp数组rightDp
        int[] rightDp = new int[length];
        rightDp[length - 1] = height[length - 1];
        for (int i = length - 2; i >= 0; i--){
            rightDp[i] = Math.max(rightDp[i + 1], height[i]);
        }
        //遍历每个下标位置即可得到能接的雨水总量
        int result = 0;
        for (int i = 0; i < length; i++){
            result += Math.min(leftDp[i],rightDp[i]) - height[i];
        }
        return result;
    }

    /**
     * 动态规划
     *  动态规划的思想：先解决子问题,再解决大问题
     *
     *  Leetcode-53 最大子序和
     *  给定一个整数数组nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素)，返回其最大和
     *  例如：nums = [-2,1,-3,4,-1,2,1,-5,-4]
     *  输出：6
     *  连续子数组[4,-1,2,1]的和最大，为 6
     */
    public static int maxSubArray(int[] nums){
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.length; i++){
            //状态转移公式
            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
            if(dp[i] > result){
                result = dp[i];
            }
        }
        return result;
    }

    public static int muxSubArray1(int[] nums){
        int result = nums[0];
        int pre = result;
        for (int i =1; i < nums.length; i++){
            pre = Math.max(pre + nums[i], nums[i]);
            if (pre > result){
                result = pre;
            }
        }
        return result;
    }


}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
